package cn.camel.algorithm.tree.avl;

/**
 * @author: Camel
 * @description: AVL树测试类
 * 用于测试AVL树的各种功能，包括插入、删除、查找、平衡性检查等
 * @date: 2025/10/15
 */
public class AVLTreeTest {

    /**
     * 测试基本插入和平衡功能
     */
    public static void testBasicInsertion() {
        System.out.println("=== 测试基本插入和平衡功能 ===");
        AVLTree tree = new AVLTree();
        
        // 测试左左情况
        System.out.println("测试左左情况（插入10, 5, 2）:");
        tree.insert(10);
        tree.insert(5);
        tree.insert(2);
        
        System.out.print("中序遍历: ");
        tree.inorder();
        System.out.println("树是否平衡: " + tree.isBalanced());
        System.out.println();
        
        // 重置树
        tree = new AVLTree();
        
        // 测试右右情况
        System.out.println("测试右右情况（插入2, 5, 10）:");
        tree.insert(2);
        tree.insert(5);
        tree.insert(10);
        
        System.out.print("中序遍历: ");
        tree.inorder();
        System.out.println("树是否平衡: " + tree.isBalanced());
        System.out.println();
        
        // 重置树
        tree = new AVLTree();
        
        // 测试左右情况
        System.out.println("测试左右情况（插入10, 5, 7）:");
        tree.insert(10);
        tree.insert(5);
        tree.insert(7);
        
        System.out.print("中序遍历: ");
        tree.inorder();
        System.out.println("树是否平衡: " + tree.isBalanced());
        System.out.println();
        
        // 重置树
        tree = new AVLTree();
        
        // 测试右左情况
        System.out.println("测试右左情况（插入5, 10, 7）:");
        tree.insert(5);
        tree.insert(10);
        tree.insert(7);
        
        System.out.print("中序遍历: ");
        tree.inorder();
        System.out.println("树是否平衡: " + tree.isBalanced());
        System.out.println();
    }

    /**
     * 测试复杂插入场景
     */
    public static void testComplexInsertion() {
        System.out.println("=== 测试复杂插入场景 ===");
        AVLTree tree = new AVLTree();
        
        int[] values = {30, 20, 40, 10, 25, 35, 50, 5, 15, 28, 38, 45, 60};
        
        System.out.println("插入序列: ");
        for (int val : values) {
            System.out.print(val + " ");
            tree.insert(val);
        }
        System.out.println();
        
        System.out.print("中序遍历: ");
        tree.inorder();
        
        System.out.print("前序遍历: ");
        tree.preorder();
        
        System.out.println("树是否平衡: " + tree.isBalanced());
        System.out.println("树的高度: " + tree.getHeight());
        System.out.println();
    }

    /**
     * 测试删除功能
     */
    public static void testDeletion() {
        System.out.println("=== 测试删除功能 ===");
        AVLTree tree = new AVLTree();
        
        // 构建一个平衡的AVL树
        int[] values = {30, 20, 40, 10, 25, 35, 50};
        for (int val : values) {
            tree.insert(val);
        }
        
        System.out.println("初始树:");
        System.out.print("中序遍历: ");
        tree.inorder();
        System.out.println("初始树是否平衡: " + tree.isBalanced());
        
        // 测试删除叶子节点
        System.out.println("删除叶子节点10:");
        tree.delete(10);
        System.out.print("中序遍历: ");
        tree.inorder();
        System.out.println("删除后是否平衡: " + tree.isBalanced());
        
        // 测试删除有一个子节点的节点
        System.out.println("删除有一个子节点的节点20:");
        tree.delete(20);
        System.out.print("中序遍历: ");
        tree.inorder();
        System.out.println("删除后是否平衡: " + tree.isBalanced());
        
        // 测试删除有两个子节点的节点
        System.out.println("删除有两个子节点的节点30:");
        tree.delete(30);
        System.out.print("中序遍历: ");
        tree.inorder();
        System.out.println("删除后是否平衡: " + tree.isBalanced());
        
        System.out.println();
    }

    /**
     * 测试查找功能
     */
    public static void testSearch() {
        System.out.println("=== 测试查找功能 ===");
        AVLTree tree = new AVLTree();
        
        int[] values = {30, 20, 40, 10, 25, 35, 50};
        for (int val : values) {
            tree.insert(val);
        }
        
        System.out.println("查找存在的值:");
        System.out.println("查找25: " + tree.search(25));
        System.out.println("查找40: " + tree.search(40));
        System.out.println("查找10: " + tree.search(10));
        
        System.out.println("查找不存在的值:");
        System.out.println("查找15: " + tree.search(15));
        System.out.println("查找55: " + tree.search(55));
        System.out.println("查找-5: " + tree.search(-5));
        
        System.out.println();
    }

    /**
     * 测试边界情况
     */
    public static void testEdgeCases() {
        System.out.println("=== 测试边界情况 ===");
        
        // 测试空树
        System.out.println("测试空树:");
        AVLTree emptyTree = new AVLTree();
        System.out.println("空树是否平衡: " + emptyTree.isBalanced());
        System.out.println("空树高度: " + emptyTree.getHeight());
        System.out.println("在空树中查找5: " + emptyTree.search(5));
        
        // 测试删除不存在的值
        System.out.println("测试删除不存在的值:");
        emptyTree.delete(100);
        System.out.println("删除不存在的值后树是否平衡: " + emptyTree.isBalanced());
        
        // 测试只有一个节点的树
        System.out.println("测试只有一个节点的树:");
        AVLTree singleNodeTree = new AVLTree();
        singleNodeTree.insert(42);
        System.out.println("单节点树是否平衡: " + singleNodeTree.isBalanced());
        System.out.println("单节点树高度: " + singleNodeTree.getHeight());
        System.out.println("查找42: " + singleNodeTree.search(42));
        System.out.println("查找43: " + singleNodeTree.search(43));
        
        System.out.println();
    }

    /**
     * 性能测试：大量数据插入
     */
    public static void testPerformance() {
        System.out.println("=== 性能测试：大量数据插入 ===");
        AVLTree tree = new AVLTree();
        
        int size = 1000;
        System.out.println("插入 " + size + " 个随机数");
        
        long startTime = System.currentTimeMillis();
        
        for (int i = 0; i < size; i++) {
            tree.insert((int)(Math.random() * 10000));
        }
        
        long endTime = System.currentTimeMillis();
        
        System.out.println("插入完成，耗时: " + (endTime - startTime) + " 毫秒");
        System.out.println("树是否平衡: " + tree.isBalanced());
        System.out.println("树的高度: " + tree.getHeight());
        System.out.println("理论最小高度（完全二叉树）: " + (int)(Math.log(size) / Math.log(2)));
        
        System.out.println();
    }

    /**
     * 主方法，运行所有测试
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        System.out.println("开始AVL树测试\n");
        
        testBasicInsertion();
        testComplexInsertion();
        testDeletion();
        testSearch();
        testEdgeCases();
        testPerformance();
        
        System.out.println("所有测试完成！");
        
        // 运行AVLTree自带的测试
        System.out.println("\n=== 运行AVLTree自带测试 ===");
        AVLTree.main(new String[0]);
    }
}